package com.company.bs2021;

/**
 * 4．复盘买卖货物最佳时机（22分)
 *
 * <p>问题描述:
 * <p>给定一个整数数组，表示连续N天的某种货物的市场价格，假定你最多可以进行
 * 两次货物交易(一买、一卖算一次货物交易，必须先买后卖)，设计一个算法来计算
 * 你所能获取的最大利润。
 *
 * <p>备注:由于库存原因，你不能同时参与多笔交易(必须在再次购买货物前出
 * 售掉原先的货物）;货物的数量都按1处理。
 *
 * <p>要求:
 * <p>完成题目对应的程序模板(MerchandiseSales）中的方法:int maxProfit(int[] prices);
 * 该方法的入口参数 prices为连续N天的某种货物的市场价格;最后输出结果为能获取的最大利润
 *
 * <p><p>提示:
 * <ul>
 * <li>1 <=prices.length <= 10000
 * <li>0<=prices[i]<=100000
 * </ul>
 *
 * <p>样例:
 * <ul>
 *  <li>样例1
 *      <br>输入: prices = [3,3,5,0,0,3,1,4]
 *      <br>输出: 6
 *  <li>样例2
 *  <br>输入: prices = [7,6,4,3,1]
 *  <br>输出: 0
 * </ul>
 *
 * @author jianf
 * @date 2021年09月09 13:37
 */
public class MerchandiseSales {
    /**
     * 解题的思路参见
     *  https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-wen-ti-by-chen-wei-f-qrz4/
     *
     * @param prices
     * @return
     */
    int maxProfit(int[] prices) {

        //定义第0天，即初始天的两次买和卖之后的值
        int buy1 = -prices[0];
        int buy2 = -prices[0];
        int sell1 = 0;
        int sell2 = 0;

        for (int i = 1; i < prices.length; i++) {
            //如果在第i天进行了交易，那么以利润大的那值保存下来。
            buy1 = Math.max(buy1, -prices[i]);
            sell1 = Math.max(sell1, buy1 + prices[i]);
            buy2 = Math.max(buy2, sell1 - prices[i]);
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }

        return sell2;
    }

    public static void main(String[] args) {

        int[] p1 = {3, 3, 5, 0, 0, 3, 1, 4};
        int[] p2 = {7, 6, 5, 4, 3};
        int[] p3 = {9, 3, 5, 0, 9, 3, 1, 40};
        //p2 = Arrays.copyOf(p2,p2.length +1);
        MerchandiseSales c = new MerchandiseSales();
        System.out.println("\n\n最大利润" + c.maxProfit(p3));
    }
}
